//
// Created by liushuai on 12/21/19.
//
#include "mypow1.h"
#include <unordered_map>
std::unordered_map<int,double> cache;
double myPow(double x, int n) {
    if (n < 0)
        return 1 / myPow(x, -n);
    if (n == 0)
        return 1;
    else {
        if (n % 2 == 0) {
            if (cache.count(n / 2))
                return cache.at(n / 2) * cache.at(n / 2);
            else {
                cache[n / 2] = myPow(x, n / 2);
                return cache.at(n / 2) * cache.at(n / 2);
            }
        } else {
            if (cache.count(n / 2))
                return cache.at(n / 2) * cache.at(n / 2) * x;
            else {
                cache[n / 2] = myPow(x, n / 2);
                return cache.at(n / 2) * cache.at(n / 2) * x;
            }
        }
    }
}
